home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / lib / jaq / dist / hash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-10-24  |  17.6 KB  |  728 lines
  1. /* 
  2.  * hash.c --
  3.  *
  4.  *    Hash package for Jaquith system
  5.  *
  6.  * Copyright 1992 Regents of the University of California
  7.  * Permission to use, copy, modify, and distribute this
  8.  * software and its documentation for any purpose and without
  9.  * fee is hereby granted, provided that the above copyright
  10.  * notice appear in all copies.  The University of California
  11.  * makes no representations about the suitability of this
  12.  * software for any purpose.  It is provided "as is" without
  13.  * express or implied warranty.
  14.  */
  15.  
  16. #ifndef lint
  17. static char rcsid[] = "$Header: /sprite/lib/forms/RCS/hash.c,v 1.0 91/01/07 18:02:37 mottsmth Exp $ SPRITE (Berkeley)";
  18. #endif /* not lint */
  19.  
  20. #include "jaquith.h"
  21.  
  22. #define AVAIL    0
  23. #define DELETED -1
  24.  
  25. static Hash_Node *FindHashNode   _ARGS_ ((Hash_Handle *hashPtr,
  26.                       Hash_Key key,
  27.                       int keyLen));
  28. static Hash_Node *FindFreeNode   _ARGS_ ((Hash_Handle *hashPtr,
  29.                       Hash_Key key, int keyLen));
  30. static void       CreateHashNode _ARGS_ ((Hash_Handle *hashPtr,
  31.                       Hash_Key key, int keyLen, 
  32.                       Hash_ClientData datum));
  33. static void       DeleteHashNode _ARGS_ ((Hash_Node *nodePtr,
  34.                       int freeFlag));
  35. static void       GrowHashTab    _ARGS_ ((Hash_Handle *hashPtr));
  36. static void       GrowStringTab  _ARGS_ ((Hash_Handle *hashPtr));
  37.  
  38.  
  39. /*
  40.  *----------------------------------------------------------------------
  41.  *
  42.  * Hash_Create --
  43.  *
  44.  *    Initialize a hash table of specified size
  45.  *
  46.  * Results:
  47.  *    ptr to hash table handle.
  48.  *
  49.  * Side effects:
  50.  *    Allocates internal table space.
  51.  *
  52.  * Note:
  53.  *      size of table must be odd.
  54.  *
  55.  *----------------------------------------------------------------------
  56.  */
  57.  
  58. Hash_Handle *
  59. Hash_Create(name, size, hashFunc, freeData)
  60.     char *name;               /* name of new hash table */
  61.     int size;                 /* number of entries */
  62.     int (*hashFunc)();        /* hashing function to use */
  63.     int freeData;             /* pass datum to Free when deallocating */
  64. {
  65.     Hash_Handle *hashPtr;
  66.  
  67.     if ((size < 0) || (size > MAXHASHSIZE) || ((size & 0x1) == 0)) {
  68.     return NULL;
  69.     }
  70.  
  71.     hashPtr = (Hash_Handle *)MEM_ALLOC("Hash_Create", sizeof(Hash_Handle));
  72.     hashPtr->name = Str_Dup(name);
  73.     hashPtr->tabSize = size;
  74.     hashPtr->tab = (Hash_Node *)
  75.     MEM_ALLOC("Hash_Create", size*sizeof(Hash_Node));
  76.     /* string space: guess 8 chars/string; hash table 1/2 full */
  77.     hashPtr->stringSize = 4*size;
  78.     hashPtr->stringTab = (char *)
  79.     MEM_ALLOC("Hash_Create", hashPtr->stringSize*sizeof(char));
  80.     hashPtr->freeData = freeData;
  81.     hashPtr->stringUsed = 0;
  82.     hashPtr->hashFunc = hashFunc;
  83.     hashPtr->tabGrowCnt = 0;
  84.     hashPtr->tabFill = 0.0;
  85.     hashPtr->stringGrowCnt = 0;
  86.     hashPtr->stringFill = 0.0;
  87.     hashPtr->insertCnt = 0;
  88.     hashPtr->deleteCnt = 0;
  89.     hashPtr->lookupCnt = 0;
  90.     hashPtr->updateCnt = 0;
  91.     hashPtr->probeCnt = 0;
  92.  
  93.     while (--size >= 0) {
  94.     hashPtr->tab[size].keyLen = AVAIL;
  95.     }
  96.  
  97.     return hashPtr;
  98. }    
  99.  
  100.  
  101. /*
  102.  *----------------------------------------------------------------------
  103.  *
  104.  * Hash_Destroy --
  105.  *
  106.  *    Free a hash table.
  107.  *
  108.  * Results:
  109.  *    None.
  110.  *
  111.  * Side effects:
  112.  *    Releases table space.
  113.  *
  114.  *----------------------------------------------------------------------
  115.  */
  116.  
  117. void
  118. Hash_Destroy(hashPtr)
  119.     Hash_Handle *hashPtr;     /* hash table handle */
  120. {
  121.     int i;
  122.  
  123.     if (hashPtr == (Hash_Handle *)NULL) {
  124.     Utils_Bailout("Hash_Destroy: Null hash ptr.\n", BAIL_PRINT);
  125.     }
  126.  
  127.     if (hashPtr->freeData) {
  128.     for (i=0; i<hashPtr->tabSize;i++) {
  129.         if (hashPtr->tab[i].keyLen != AVAIL) {
  130.         MEM_FREE("Hash_Destroy", (char *)hashPtr->tab[i].datum);
  131.         }
  132.     }
  133.     }
  134.     MEM_FREE("Hash_Destroy", (char *)hashPtr->name);
  135.     MEM_FREE("Hash_Destroy", (char *)hashPtr->tab);
  136.     MEM_FREE("Hash_Destroy", (char *)hashPtr->stringTab);
  137.     MEM_FREE("Hash_Destroy", (char *)hashPtr);
  138.  
  139. }
  140.  
  141.  
  142. /*
  143.  *----------------------------------------------------------------------
  144.  *
  145.  * Hash_Insert --
  146.  *
  147.  *    Use key to add an entry to table.
  148.  *
  149.  * Results:
  150.  *    None.
  151.  *
  152.  * Side effects:
  153.  *    None.
  154.  *
  155.  *----------------------------------------------------------------------
  156.  */
  157.  
  158. int
  159. Hash_Insert(hashPtr, key, keyLen, datum)
  160.     Hash_Handle *hashPtr;     /* hash table handle */
  161.     Hash_Key key;             /* key for insertion */
  162.     int keyLen;               /* size of key */
  163.     Hash_ClientData datum;    /* value of interest */
  164. {
  165.     if (hashPtr == (Hash_Handle *)NULL) {
  166.     Utils_Bailout("Hash_Insert: Null hash ptr.\n", BAIL_PRINT);
  167.     }
  168.  
  169.     if (keyLen < 1) {
  170.     Utils_Bailout("Hash_Insert: Bad key length.\n", BAIL_PRINT);
  171.     }
  172.  
  173.     if (FindHashNode(hashPtr, key, keyLen) != (Hash_Node *)NULL) {
  174.     return T_FAILURE;
  175.     }
  176.  
  177.     CreateHashNode(hashPtr, key, keyLen, datum);
  178.     hashPtr->insertCnt++;
  179.     return T_SUCCESS;
  180. }
  181.  
  182.  
  183. /*
  184.  *----------------------------------------------------------------------
  185.  *
  186.  * Hash_Update --
  187.  *
  188.  *    Use key to modify an entry in table.
  189.  *
  190.  * Results:
  191.  *    None.
  192.  *
  193.  * Side effects:
  194.  *    None.
  195.  *
  196.  *----------------------------------------------------------------------
  197.  */
  198.  
  199. int
  200. Hash_Update(hashPtr, key, keyLen, datum)
  201.     Hash_Handle *hashPtr;     /* hash table handle */
  202.     Hash_Key key;             /* key for insertion */
  203.     int keyLen;               /* size of key */
  204.     Hash_ClientData datum;    /* value of interest */
  205. {
  206.     Hash_Node *nodePtr;
  207.  
  208.     if (hashPtr == (Hash_Handle *)NULL) {
  209.     Utils_Bailout("Hash_Update: Null hash ptr.\n", BAIL_PRINT);
  210.     }
  211.     
  212.     if (keyLen < 1) {
  213.     Utils_Bailout("Hash_Update: Bad key length.\n", BAIL_PRINT);
  214.     }
  215.  
  216.     if ((nodePtr=FindHashNode(hashPtr, key, keyLen)) ==    (Hash_Node *)NULL) {
  217.     return T_FAILURE;
  218.     }
  219.  
  220.     nodePtr->datum = datum;
  221.     hashPtr->updateCnt++;
  222.     return T_SUCCESS;
  223. }
  224.  
  225.  
  226. /*
  227.  *----------------------------------------------------------------------
  228.  *
  229.  * Hash_Delete --
  230.  *
  231.  *    Remove an item from the table.
  232.  *
  233.  * Results:
  234.  *    None.
  235.  *
  236.  * Side effects:
  237.  *    None.
  238.  *
  239.  *----------------------------------------------------------------------
  240.  */
  241.  
  242. int
  243. Hash_Delete(hashPtr, key, keyLen)
  244.     Hash_Handle *hashPtr;     /* hash table handle */
  245.     Hash_Key key;             /* key for item to be removed */
  246.     int keyLen;               /* size of key */
  247. {
  248.     Hash_Node *nodePtr;
  249.  
  250.     if (hashPtr == (Hash_Handle *)NULL) {
  251.     Utils_Bailout("Hash_Delete: Null hash ptr.\n", BAIL_PRINT);
  252.     }
  253.     
  254.     if (keyLen < 1) {
  255.     Utils_Bailout("Hash_Delete: Bad key length.\n", BAIL_PRINT);
  256.     }
  257.  
  258.     if ((nodePtr=FindHashNode(hashPtr, key, keyLen)) ==    (Hash_Node *)NULL) {
  259.     return T_FAILURE;
  260.     }
  261.  
  262.     DeleteHashNode(nodePtr, hashPtr->freeData);
  263.     hashPtr->deleteCnt++;
  264.     return T_SUCCESS;
  265. }
  266.  
  267.  
  268. /*
  269.  *----------------------------------------------------------------------
  270.  *
  271.  * Hash_Lookup --
  272.  *
  273.  *    Find an item by key in the table
  274.  *
  275.  * Results:
  276.  *    Corresponding client datum and a return code
  277.  *
  278.  * Side effects:
  279.  *    None.
  280.  *
  281.  *----------------------------------------------------------------------
  282.  */
  283.  
  284. int
  285. Hash_Lookup(hashPtr, key, keyLen, datumPtr)
  286.     Hash_Handle *hashPtr;     /* hash table handle */
  287.     Hash_Key key;             /* key for item to be lookup up */
  288.     int keyLen;               /* size of key */
  289.     Hash_ClientData *datumPtr;/* return value */
  290. {
  291.     Hash_Node *nodePtr;
  292.  
  293.     if (hashPtr == (Hash_Handle *)NULL) {
  294.     Utils_Bailout("Hash_Lookup: Null hash ptr.\n", BAIL_PRINT);
  295.     }
  296.     
  297.     if (keyLen < 1) {
  298.     Utils_Bailout("Hash_Lookup: Bad key length.\n", BAIL_PRINT);
  299.     }
  300.  
  301.     if ((nodePtr=FindHashNode(hashPtr, key, keyLen)) ==    (Hash_Node *)NULL) {
  302.     return T_FAILURE;
  303.     }
  304.  
  305.     *datumPtr = nodePtr->datum;
  306.     hashPtr->lookupCnt++;
  307.     return T_SUCCESS;
  308. }
  309.  
  310.  
  311. /*
  312.  *----------------------------------------------------------------------
  313.  *
  314.  * Hash_Iterate --
  315.  *
  316.  *    Invoke callback function for each item in table
  317.  *
  318.  * Results:
  319.  *    
  320.  *
  321.  * Side effects:
  322.  *    Calls user function.
  323.  *
  324.  * The callback function is provided with:                   
  325.  *   hash ptr  : so it knows what table it's operating on        
  326.  *   key    : for processing                                  
  327.  *   keyLen : for processing                                  
  328.  *   datum  : for processing                                  
  329.  *   callVal: Arbitray ptr provided by Hash_Iterate caller.
  330.  *                                                           
  331.  * Callback routine must not call Hash_*  for this table.
  332.  *                                                           
  333.  * We respond to the return code as follows:                 
  334.  *    = HASH_ITER_REMOVE_STOP : remove item from table and stop
  335.  *    = HASH_ITER_REMOVE_CONT : remove item from table and continue 
  336.  *    = HASH_ITER_STOP : stop
  337.  *    = HASH_ITER_CONTINUE  : do nothing to the item and continue
  338.  *
  339.  *----------------------------------------------------------------------
  340.  */
  341.  
  342. void
  343. Hash_Iterate(hashPtr, func, callVal) 
  344.     Hash_Handle *hashPtr;        /* hash table handle */
  345.     int (*func)();            /* callback function */
  346.     int *callVal;             /* arbitrary value passed to func */
  347. {
  348.     int i;
  349.     int retCode;
  350.     Hash_Node *nodePtr;
  351.     
  352.     if (hashPtr == (Hash_Handle *)NULL) {
  353.     Utils_Bailout("Hash_Iterate: Null hash ptr.\n", BAIL_PRINT);
  354.     }
  355.  
  356.     for (i=0,nodePtr=hashPtr->tab; i<hashPtr->tabSize; i++,nodePtr++) {
  357.     if ((nodePtr->keyLen != DELETED) && (nodePtr->keyLen != AVAIL)) {
  358.         retCode = (*func)(hashPtr, nodePtr->key,
  359.             nodePtr->keyLen, nodePtr->datum, callVal);
  360.         if (retCode == HASH_ITER_STOP) {
  361.         break;
  362.         } else if (retCode == HASH_ITER_CONTINUE) {
  363.         /* do nothing */
  364.         } else if (retCode == HASH_ITER_REMOVE_CONT) {
  365.         DeleteHashNode(nodePtr, hashPtr->freeData);
  366.         } else if (retCode == HASH_ITER_REMOVE_STOP) {
  367.         DeleteHashNode(nodePtr, hashPtr->freeData);
  368.         break;
  369.         } else {
  370.         Utils_Bailout("Hash_Iterate: Unknown return code from callback function.\n", BAIL_PRINT);
  371.         }
  372.     }
  373.     }
  374.  
  375. }
  376.  
  377.  
  378.  
  379. /*
  380.  *----------------------------------------------------------------------
  381.  *
  382.  * Hash_Stats --
  383.  *
  384.  *    Return some mildly interesting numbers about performance
  385.  *
  386.  * Results:
  387.  *    
  388.  *
  389.  * Side effects:
  390.  *    None.
  391.  *
  392.  *----------------------------------------------------------------------
  393.  */
  394.  
  395. void
  396. Hash_Stats(hashPtr, statPtr)
  397.     Hash_Handle *hashPtr;        /* hash table handle */
  398.     Hash_Stat *statPtr;       /* receiving data structure */
  399. {
  400.  
  401.     if (hashPtr == (Hash_Handle *)NULL) {
  402.     Utils_Bailout("Hash_Stats: Null hash ptr.\n", BAIL_PRINT);
  403.     }
  404.  
  405.     statPtr->tabSize = hashPtr->tabSize;
  406.     statPtr->tabGrowCnt = hashPtr->tabGrowCnt;
  407.     if (hashPtr->tabGrowCnt == 0) {
  408.     statPtr->avgTabFill = 0.0;
  409.     } else {
  410.     statPtr->avgTabFill =
  411.         hashPtr->tabFill / (float)hashPtr->tabGrowCnt;
  412.     }
  413.  
  414.     statPtr->stringSize = hashPtr->stringSize;
  415.     statPtr->stringGrowCnt = hashPtr->stringGrowCnt;
  416.     if (hashPtr->stringGrowCnt == 0) {
  417.     statPtr->avgStringFill = 0.0;
  418.     } else {
  419.     statPtr->avgStringFill =
  420.         hashPtr->stringFill / (float)hashPtr->stringGrowCnt;
  421.     }
  422.  
  423.     statPtr->insertCnt = hashPtr->insertCnt;
  424.     statPtr->deleteCnt = hashPtr->deleteCnt;
  425.     statPtr->lookupCnt = hashPtr->lookupCnt;
  426.     statPtr->updateCnt = hashPtr->updateCnt;
  427.     statPtr->avgProbeCnt = (hashPtr->insertCnt+
  428.                 hashPtr->deleteCnt+
  429.                 hashPtr->lookupCnt) / (float)hashPtr->probeCnt;
  430. }
  431.  
  432.  
  433. /*
  434.  *----------------------------------------------------------------------
  435.  *
  436.  * FindHashNode --
  437.  *
  438.  *    Internal location routine
  439.  *
  440.  * Results:
  441.  *    returns a pointer to a Hash_Node.
  442.  *
  443.  * Side effects:
  444.  *    None.
  445.  *
  446.  * Note:
  447.  *      Stupid algorithm. Probe function is just a linear search,
  448.  *      skipping every other location.
  449.  *
  450.  *----------------------------------------------------------------------
  451.  */
  452.  
  453. static Hash_Node *
  454. FindHashNode(hashPtr, key, keyLen)
  455.     Hash_Handle *hashPtr;     /* hash table handle */
  456.     Hash_Key key;             /* lookup key */
  457.     int keyLen;               /* size of key */
  458. {
  459.     int loc;
  460.     int startLoc;
  461.     char *nodeString;
  462.     int nodeStringLen;
  463.  
  464.     loc = startLoc = (*hashPtr->hashFunc)(key, keyLen, hashPtr->tabSize);
  465. /*
  466.     fprintf(stderr,"hash: lookup key %s %d at loc %d...",  key, keyLen, loc);
  467. */
  468.     do {
  469.     nodeString = hashPtr->tab[loc].key;
  470.     nodeStringLen = hashPtr->tab[loc].keyLen;
  471.     if ((hashPtr->tab[loc].keyLen == keyLen) &&
  472.         (bcmp(nodeString, key, keyLen) == 0)) {
  473. /*
  474.         fprintf(stderr,"found at %d, val %x\n",
  475.             loc, hashPtr->tab[loc].datum);
  476. */
  477.         return &hashPtr->tab[loc];
  478.     }
  479.     hashPtr->probeCnt++;
  480.     loc = (loc+2) % hashPtr->tabSize;
  481.     } while ((loc != startLoc) && (nodeStringLen != AVAIL));
  482. /*
  483.     fprintf(stderr,"not found\n");
  484. */
  485.     return NULL;
  486.  
  487. }
  488.  
  489.  
  490. /*
  491.  *----------------------------------------------------------------------
  492.  *
  493.  * FindFreeNode --
  494.  *
  495.  *    Internal location routine
  496.  *
  497.  * Results:
  498.  *    returns a pointer to available Hash_Node.
  499.  *
  500.  * Side effects:
  501.  *    None.
  502.  *
  503.  * Note:
  504.  *      Stupid algorithm. Probe function is just a linear search,
  505.  *      skipping every other location.
  506.  *
  507.  *----------------------------------------------------------------------
  508.  */
  509.  
  510. static Hash_Node *
  511. FindFreeNode(hashPtr, key, keyLen)
  512.     Hash_Handle *hashPtr;        /* hash table handle */
  513.     Hash_Key key;          /* lookup key */
  514.     int keyLen;               /* size of key */
  515. {
  516.     int loc;
  517.     int startLoc;
  518.     int nodeStringLen;
  519.  
  520.     loc = startLoc =
  521.     (*hashPtr->hashFunc)(key, keyLen, hashPtr->tabSize);
  522.  
  523.     do {
  524.     nodeStringLen = hashPtr->tab[loc].keyLen;
  525.     if ((nodeStringLen == AVAIL) || (nodeStringLen == DELETED)) {
  526.         return &hashPtr->tab[loc];
  527.     }
  528.     loc = (loc+2) % hashPtr->tabSize;
  529.     } while (loc != startLoc);
  530.  
  531.     return NULL;
  532.  
  533. }
  534.  
  535.  
  536. /*
  537.  *----------------------------------------------------------------------
  538.  *
  539.  * CreateHashNode --
  540.  *
  541.  *    Internal allocation routine
  542.  *
  543.  * Results:
  544.  *    returns a pointer to a new filled in Hash_Node
  545.  *
  546.  * Side effects:
  547.  *    None.
  548.  *
  549.  * Note:
  550.  *      Stupid algorithm.
  551.  *
  552.  *----------------------------------------------------------------------
  553.  */
  554.  
  555. static void
  556. CreateHashNode(hashPtr, key, keyLen, datum)
  557.     Hash_Handle *hashPtr;     /* hash table handle */
  558.     Hash_Key key;             /* new key...        */
  559.     Hash_ClientData datum;    /*           and value */
  560. {
  561.     Hash_Node *nodePtr;
  562.     
  563.     if ((nodePtr=FindFreeNode(hashPtr, key, keyLen)) == (Hash_Node *)NULL) {
  564.     GrowHashTab(hashPtr);
  565.     if ((nodePtr=FindFreeNode(hashPtr,key, keyLen)) == (Hash_Node *)NULL) {
  566.         fprintf(stderr, "CreateHashNode: Couldn't find free node\n");
  567.         fprintf("die %s\n", 0);
  568.         exit(-1);
  569.     }
  570.     }
  571.  
  572.     while (hashPtr->stringUsed+keyLen > hashPtr->stringSize) {
  573.     GrowStringTab(hashPtr);
  574.     }
  575. /*
  576.     fprintf(stderr, "Create: assigned %d to %s, %x\n",
  577.         nodePtr-hashPtr->tab, key, datum);
  578. */
  579.     nodePtr->datum = datum;
  580.     nodePtr->key = hashPtr->stringTab+hashPtr->stringUsed;
  581.     nodePtr->keyLen = keyLen;
  582.     bcopy(key, nodePtr->key, keyLen);
  583.     hashPtr->stringUsed += keyLen;
  584. }
  585.  
  586.  
  587. /*
  588.  *----------------------------------------------------------------------
  589.  *
  590.  * DeleteHashNode --
  591.  *
  592.  *    Internal deallocation routine
  593.  *
  594.  * Results:
  595.  *    None.
  596.  *
  597.  * Side effects:
  598.  *    None.
  599.  *
  600.  *----------------------------------------------------------------------
  601.  */
  602.  
  603. static void
  604. DeleteHashNode(nodePtr, freeData)
  605.     Hash_Node *nodePtr;       /* node to be removed */
  606.     int freeData;
  607. {
  608.  
  609.     nodePtr->keyLen = DELETED;
  610.     if (freeData) {
  611.     MEM_FREE("DeleteHashNode", (char *)nodePtr->datum);
  612.     }
  613.     nodePtr->datum = (Hash_ClientData) -1;
  614.  
  615. }
  616.  
  617.  
  618. /*
  619.  *----------------------------------------------------------------------
  620.  *
  621.  * GrowHashTab --
  622.  *
  623.  *    Internal hash table expansion routine
  624.  *
  625.  * Results:
  626.  *    Grown table with data copied over.
  627.  *
  628.  * Side effects:
  629.  *    None.
  630.  *
  631.  *----------------------------------------------------------------------
  632.  */
  633.  
  634. static void
  635. GrowHashTab(hashPtr)
  636.     Hash_Handle *hashPtr;        /* hash table handle */
  637. {
  638.     int i;
  639.     int used;
  640.     int oldSize = hashPtr->tabSize;
  641.     Hash_Node *oldTab = hashPtr->tab;
  642.     Hash_Node *oldPtr;
  643.     Hash_Node *newPtr;
  644. /*
  645.     fprintf(stderr, "GrowHashTab\n");
  646. */
  647.     hashPtr->tabSize = 2*oldSize+1;
  648.     hashPtr->tab = 
  649.     (Hash_Node *)MEM_ALLOC("GrowHashTab",hashPtr->tabSize*sizeof(Hash_Node));
  650.  
  651.     for (i=0,newPtr=hashPtr->tab; i<hashPtr->tabSize; i++,newPtr++) {
  652.     newPtr->keyLen = AVAIL;
  653.     }
  654.  
  655.     for (i=0,oldPtr=oldTab,used=0; i<oldSize; i++,oldPtr++) {
  656.     if ((oldPtr->keyLen != AVAIL) && (oldPtr->keyLen != DELETED)) {
  657.         used++;
  658.         if ((newPtr=FindFreeNode(hashPtr, oldPtr->key, oldPtr->keyLen))
  659.         == (Hash_Node *)NULL) {
  660.         fprintf(stderr, "Error growing hash table: %s\n", hashPtr->name);
  661.         } else {
  662.         newPtr->key = oldPtr->key;
  663.         newPtr->keyLen = oldPtr->keyLen;
  664.         newPtr->datum = oldPtr->datum;
  665.         }
  666.     }
  667.     }
  668.  
  669.     MEM_FREE("GrowHashTab", (char *)oldTab);
  670.     hashPtr->tabGrowCnt++;
  671.     hashPtr->tabFill += used / (float)oldSize;
  672. }
  673.  
  674.  
  675. /*
  676.  *----------------------------------------------------------------------
  677.  *
  678.  * GrowStringTab --
  679.  *
  680.  *    Internal string table expansion routine
  681.  *
  682.  * Results:
  683.  *    Grown table with data copied over.
  684.  *
  685.  * Side effects:
  686.  *    None.
  687.  *
  688.  *----------------------------------------------------------------------
  689.  */
  690.  
  691. static void
  692. GrowStringTab(hashPtr)
  693.     Hash_Handle *hashPtr;        /* hash table handle */
  694. {
  695.     int oldSize = hashPtr->stringSize;
  696.     int newSize;
  697.     int i;
  698.     int keyLen;
  699.     int used = 0;
  700.     char *curPtr;
  701.     char *oldTab = hashPtr->stringTab;
  702.     Hash_Node *nodePtr;
  703. /*
  704.     fprintf(stderr, "GrowStringTab\n");
  705. */
  706.     newSize = 2*oldSize;
  707.  
  708.     hashPtr->stringTab = curPtr =
  709.     (char *)MEM_ALLOC("GrowStringTab",newSize*sizeof(char));
  710.  
  711.     for (i=0,nodePtr=hashPtr->tab; i<hashPtr->tabSize; i++, nodePtr++) {
  712.     if ((nodePtr->keyLen != AVAIL) && (nodePtr->keyLen != DELETED)) {
  713.         keyLen = nodePtr->keyLen;
  714.         bcopy((char *)nodePtr->key, curPtr, keyLen);
  715.         nodePtr->key = curPtr;
  716.         used += keyLen;
  717.         curPtr += keyLen;
  718.     }
  719.     }
  720.  
  721.     hashPtr->stringUsed = used;
  722.     hashPtr->stringSize = newSize;
  723.     MEM_FREE("GrowStringTab", oldTab);
  724.     hashPtr->stringGrowCnt++;
  725.     hashPtr->stringFill += used / (float)oldSize;
  726.  
  727. }
  728.